//设计一个算法，找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。 
//
// 示例 1： 
//
// 
//输入：nums = [5,6,5], target = 11
//输出：[[5,6]] 
//
// 示例 2： 
//
// 
//输入：nums = [5,6,5,6], target = 11
//输出：[[5,6],[5,6]] 
//
// 提示： 
//
// 
// nums.length <= 100000 
// -10⁵ <= nums[i], target <= 10⁵ 
// 
//
// Related Topics 数组 哈希表 双指针 计数 排序 👍 60 👎 0


package LeetCode.editor.cn;


import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author ldltd
 * @date 2025-09-11 14:23:37
 * @description 面试题 16.24.数对和
 
 */
 
public class PairsWithSumLcci {
    public static void main(String[] args) {
    //测试代码
    PairsWithSumLcci fun = new PairsWithSumLcci();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public List<List<Integer>> pairSums1(int[] nums, int target) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int num : nums) {
            map.merge(num,1,Integer::sum);
        }
        List<List<Integer>> ans=new java.util.ArrayList<>();
        for (int num : nums) {
            int complement=target-num;
            if(map.getOrDefault(num,0)>0&&map.getOrDefault(complement,0)>0){
                if(num==complement&&map.get(num)<2){
                    continue;
                }
                ans.add(java.util.Arrays.asList(num,complement));
                map.put(num,map.get(num)-1);
                map.put(complement,map.get(complement)-1);
            }
        }
        return ans;
    }
    //双指针
    public List<List<Integer>> pairSums(int[] nums, int target) {
        java.util.Arrays.sort(nums);
        List<List<Integer>> ans = new java.util.ArrayList<>();
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                ans.add(java.util.Arrays.asList(nums[left], nums[right]));
                left++;
                right--;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
        return ans;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
